package Leetcode.动态规划;

import java.util.Arrays;

public class NMSUM2 {

    public static void Sum(int[] arr, int m) {
        // 数组长度
        int n = arr.length;
        // 创建辅助数组b和SUM
        int[] b = new int[n+1];
        int[] sum = new int[n+1];

        // 初始化b数组和SUM数组的第一个元素
        b[0] = 0; // 一个子段获或者数字都不取时
        sum[1] = arr[0]; // 初始化SUM数组的第一个元素

        // 遍历数组，寻找m个子段的最大和
        for (int j = 1; j <= m; j++) {
            // 计算当前子段的和
            b[j] = b[j - 1] + arr[j - 1];
            // 重置SUM数组的当前元素，因为我们需要计算下一个子段的和
            sum[j - 1] = -1; // 第j轮 SUM[j-1]表示原来的 SUM[j-1][j] 无意义，设置为-1
            int temp = b[j]; // 临时变量，用于存储SUM[i][j]

            // 遍历数组，寻找下一个子段的和
            for (int i = j + 1; i <= n - m + j; i++) {
                // 计算当前子段的和
                b[i] = b[i - 1] + arr[i - 1];
                // 更新SUM数组，如果当前子段的和大于之前保存的值
                if (sum[i - 1] + arr[i - 1] > b[i]) {
                    b[i] = sum[i - 1] + arr[i - 1];
                }
                // 更新临时变量，用于存储SUM[i][j]
                sum[i - 1] = temp;
                if (b[i] > temp) {
                    temp = b[i]; // temp 记录SUM[i][j]
                }
            }
            // 更新SUM数组的最后一个元素
            sum[j + n - m] = temp;
        }
//        System.out.println(Arrays.toString(b));
//
//        System.out.println();
//        System.out.println(Arrays.toString(sum));

        // 输出结果
        System.out.println(sum[n]);
    }
    public static void main(String[] args) {
        int[] a = {1, -2, 3, 4, -5, -6, 7, 18, -9};
        Sum(a, 2);
    }

}